/*************************************************************************
	> File Name: 008.实现自己的sort函数.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 五  1/ 7 11:35:13 2022
 ************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

ostream &operator<<(ostream &out, const vector<int> &a) {
    for (auto x : a) {
        out << x << " ";
    }
    return out;
}

bool cmp1(int a, int b) {
    return a > b; //当a > b的时候，a排在b前面，也就是从大到小排序
}

namespace maureen {

class CMP {
public :
    CMP(int z = 0) : z(z) {} //z = 0 less, z = 1 greater
    bool operator()(int a, int b) {
        return (a < b) ^ !!(z);
    }
    int z;
};

//cmp是一个函数指针对象，本质是对象，表现得像个函数指针，返回值是bool，传入参数是两个int
void sort(int *arr, int l, int r, function<bool(int, int)> cmp = CMP()) {
    //就是快速排序
    if (l >= r) return ;
    int x = l, y = r, z = arr[(l + r) >> 1];
    do {
        while (cmp(arr[x], z)) ++x;
        while (cmp(z, arr[y])) --y;
        if (x <= y) {
            swap(arr[x], arr[y]);
            ++x, --y;
        }
    } while (x <= y);
    sort(arr, l, y, cmp);
    sort(arr, x, r, cmp);
    return ;
}

}; //end of maureen

int main() {
    vector<int> arr;
    int n;
    cin >> n;
    while (n--) { int a; cin >> a, arr.push_back(a); }
    //sort(arr.begin(), arr.end(), cmp1);
    sort(arr.begin(), arr.end(), maureen::CMP());//CMP()就是一个匿名对象，第三个位置放置的应该是函数名，而仿函数的函数名就是对象名
    //系统sort函数之所以能传入可调用对象，是因为使用了function这个模板类
    cout << arr << endl;


    // ====使用自己写的sort函数
    int arr2[5] = {6, 8, 4, 5, 1};

    maureen::sort(arr2, 0, 4); //默认情况从小到大排
    for (int i = 0; i < 5; i++) {
        cout << arr2[i] << " ";
    }
    cout << endl;

    //从大到小排: 使用自定义函数
    maureen::sort(arr2, 0, 4, cmp1);
    for (int i = 0; i < 5; i++) {
        cout << arr2[i] << " ";
    }
    cout << endl;

    maureen::sort(arr2, 0, 4); //默认情况从小到大排
    for (int i = 0; i < 5; i++) {
        cout << arr2[i] << " ";
    }
    cout << endl;

    //从大到小排: 使用仿函数
    maureen::sort(arr2, 0, 4, maureen::CMP(1));
    for (int i = 0; i < 5; i++) {
        cout << arr2[i] << " ";
    }
    cout << endl;

    return 0;
}
//运行结果：
//5  #输入
//1 4 2 0 9 #输入
//0 1 2 4 9 #输出
//1 4 5 6 8 #输出
//8 6 5 4 1 #输出
//1 4 5 6 8 #输出
//8 6 5 4 1 #输出
